package org.basis.algorithm.sort.practice;

import org.basis.algorithm.common.SortUtil;

import java.util.Arrays;

/**
 * 二分查找练习
 *
 * @author Mr_wenpan@163.com 2022/03/03 17:43
 */
public class BinarySearch {

    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            Arrays.sort(arr);
            SortUtil.printArr(arr);
//            boolean exists = exists(arr, 10);
            boolean exists = exists2(arr, 10);
            System.out.println(exists);
        }
    }

    public static boolean exists(int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            return false;
        }
        return process(arr, 0, arr.length - 1, target);
    }

    /**
     * 递归解法
     */
    public static boolean process(int[] arr, int l, int r, int target) {
        // base case
        if (l > r) {
            return false;
        }
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] > target) {
            return process(arr, l, mid - 1, target);
        } else {
            return process(arr, mid + 1, r, target);
        }
    }

    /**
     * 在有重复数的有序数组中查找第一个等于target的索引下标
     */
    public static int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        // 记录和target相等位置的下标
        int ans = -1;
        while (l <= r) {
            // 防止溢出
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) {
                // 中点的下标暂时记录下来
                ans = mid;
                // 由于要求等于target的最小的下标，所以这里移动右边界r，反之则移动左边界l
                r = mid - 1;
            } else if (arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return ans;
    }

    /**
     * 迭代解法
     */
    public static boolean exists2(int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            return false;
        }
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
}
